package com.xzz.sort;

import java.util.Arrays;

/**
 * @author: hhz
 * @create: 2021-12-14 14:16
 * 堆排序
 * 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
 * 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
 * 从最后一个非叶节点 :int i = (arr.length-1)/2 = arr.length/2-1
 **/
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{4,6,8,5,9,2,3,7};
        int length = arr.length;
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            maxHeap(arr, i, length);
        }
        System.out.println("第一种方法构建大顶堆");
        System.out.println(Arrays.toString(arr));

        int[] arr2 = new int[]{4,6,8,5,9,2,3,7};
        int length2 = arr2.length;
        for (int i = arr2.length / 2 - 1; i >= 0; i--) {
            maxHeap2(arr2, i, length2);
        }
        System.out.println("第二种方法构建大顶堆");
        System.out.println(Arrays.toString(arr2));
        maxHeapSort(arr);
        System.out.println("利用大顶堆进行升序排序");
        System.out.println(Arrays.toString(arr));

        int[] arr3 = new int[]{4,6,8,5,9,2,3,7};
        int length3 = arr3.length;
        for (int i = arr3.length / 2 - 1; i >= 0; i--) {
            minHeap(arr3, i, length3);
        }
        System.out.println("第一种方法构建小顶堆");
        System.out.println(Arrays.toString(arr3));
        minHeapSort(arr3);
        System.out.println("利用小顶堆进行降序排序");
        System.out.println(Arrays.toString(arr3));
        int[] arr4 = new int[]{4,6,8,5,9,2,3,7};
        int length4 = arr4.length;
        for (int i = arr4.length / 2 - 1; i >= 0; i--) {
            minHeap2(arr4, i, length4);
        }
        System.out.println("第二种方法构建小顶堆");
        System.out.println(Arrays.toString(arr4));
    }
    //构建大顶堆
    public static void maxHeap(int[] arr,int i,int length){
        int max = i;
        //左子节点
        int left = 2*i+1;
        //右子节点
        int right = 2*i+2;
        if(left < length && arr[left]>arr[max]){
            max = left;
        }
        if(right<length && arr[right]>arr[max]){
            max = right;
        }
        if(max != i){
            swap(arr,i,max);
            maxHeap(arr,max,length);
        }
    }
    //构建大顶堆 第二种方法
    public static void maxHeap2(int[] arr,int i,int length){
        int temp = arr[i];
        //左子节点 int j=2*i+1;
        for(int j=2*i+1;j<length;j=j*2+1){
            //先指向左节点 如果右节点>左节点 则指向右节点
            if(j+1<length && arr[j+1]>arr[j]){
                j++;
            }
            //如果指向的节点大于需要调整的节点，则交换，交换后 j=2*j+1 指向被交换(调整)节点的左子节点
            if(arr[j]>temp){
                swap(arr,j,i);
                //将i赋值为j 进入下一次的for
                i=j;
            }else {
                break;
            }
        }
    }
    //利用大顶堆升序排序
    public static void maxHeapSort(int[] arr){
        int length = arr.length;
        for (int i = arr.length - 1; i >= 0; i--) {
            //根节点(第一个节点)与最后一个叶子节点交换
            swap(arr,0,i);
            //交换后剩下的节点从根节点处重新构建大顶堆
            maxHeap(arr,0,--length);
        }
    }
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //构建小顶堆
    public static void minHeap(int[] arr,int i,int length){
        //默认该节点是最小值
        int min = i;
        //左子节点
        int left = 2*i+1;
        //右子节点
        int right = 2*i+2;
        if(left < length && arr[left]<arr[min]){
            //如果有左节点，并且左节点的值更小，
            min = left;
        }
        if(right<length && arr[right]<arr[min]){
            //如果有右节点，并且右节点的值更小，
            min = right;
        }
        if(min != i){
            //如果最小值不是当前节点，则交换当前节点和最小值的节点
            swap(arr,i,min);
            //互换之后，子节点的值变了，如果该子节点也有自己的子节点，也需要进行调整
            minHeap(arr,min,length);
        }
    }
    //构建小顶堆 第二种方法
    public static void minHeap2(int[] arr,int i,int length){
        int temp = arr[i];
        //左子节点 int j=2*i+1;
        for(int j=2*i+1;j<length;j=j*2+1){
            //先指向左节点 如果右节点<左节点 则指向右节点
            if(j+1<length && arr[j+1]<arr[j]){
                j++;
            }
            //如果指向的节点小于需要调整的节点，则交换，交换后 j=2*j+1 指向被交换(调整)节点的左子节点
            if(arr[j]<temp){
                swap(arr,j,i);
                //将i赋值为j 进入下一次的for
                i=j;
            }else {
                break;
            }
        }
    }
    //利用小顶堆降序排序
    public static void minHeapSort(int[] arr){
        int length = arr.length;
        for (int i = arr.length - 1; i >= 0; i--) {
            //根节点(第一个节点)与最后一个叶子节点交换
            swap(arr,0,i);
            //交换后剩下的节点从根节点处重新构建小顶堆
            minHeap(arr,0,--length);
        }
    }
}
